// 动态规划 - 核心 5 步：
// 1. 确定状态表示 - 根据 题目要求，经验(以 i,j 位置为结尾/开始......)，发现重复子问题 确定状态表示
// 2. 推导状态转移方程: dp[i] = ?
//    用 之前的状态 或者 之后的状态 推导当前的状态（根据最近一步划分问题）
// 3. 初始化：保证填表时不越界，结合多开数组的技巧
// 4. 确定填表顺序：填写当前状态值的时候，所需状态的值已经计算过了
// 5. 返回值：结合题目要求 + 状态表示

// 技巧：
// 01 背包问题：使用滚动数组进行优化，删除横坐标，从右往左填表
// 完全背包问题：使用滚动数组进行优化，删除横坐标，从左往右填表

// 例题 8:
// 给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
//
//        完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。
//        例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
//
//        示例 1：
//
//        输入：n = 12
//        输出：3
//        解释：12 = 4 + 4 + 4
//        示例 2：
//
//        输入：n = 13
//        输出：2
//        解释：13 = 4 + 9
//
//        提示：
//
//        1 <= n <= 104

// 解题思路:
// dp[i][j] 表示从 [0, i] 区间内选取完全平方数，总和正好等于 j 的最少数字数
// 初始化：
// dp[0][j] = INF, 1 <= j <= n, INF = 0x3f3f3f3f
// 根据最后一个数字分情况讨论：
// 不选 i 位置的数字: dp[i][j] = dp[i - 1][j]
// 选 i 位置的数字: dp[i][j] = dp[i][j - i * i] + 1
// 选取两种情况下的最小值

public class NumSquares {
    public int numSquares(int n) {
        int t = (int)Math.sqrt(n);
        int INF = 0x3f3f3f3f;

        int[][] dp = new int[t + 1][n + 1];

        for(int j = 1; j <= n; j++){
            dp[0][j] = INF;
        }

        for(int i = 1; i <= t; i++){
            for(int j = 0; j <= n; j++){
                dp[i][j] = dp[i - 1][j];
                if(j >= i * i && dp[i][j - i * i] != INF){
                    dp[i][j] = Math.min(dp[i][j], dp[i][j - i * i] + 1);
                }
            }
        }
        return dp[t][n];
    }
}
